public class Demo1 {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    public int numIslands(char[][] grid) {
        int count = 0;
        m = grid.length;
        n = grid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    void dfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }

    class Solution {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int m, n, sum, count;
        public int maxAreaOfIsland(int[][] grid) {
            m = grid.length;
            n = grid[0].length;
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == 1) {
                        dfs(grid, i, j);
                        sum = Math.max(sum, count);
                        count = 0;
                    }
                }
            }
            return sum;
        }
        void dfs(int[][] grid, int i, int j) {
            grid[i][j] = 0;
            count++;
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                    dfs(grid, x, y);
                }
            }
        }
    }

    class Solution2 {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int m, n;
        public void solve(char[][] board) {
            m = board.length;
            n = board[0].length;
            for(int i = 0; i < m; i++) {
                if(board[i][0] == 'O') {
                    dfs(board, i, 0);
                }
                if(board[i][n-1] == 'O') {
                    dfs(board, i, n-1);
                }
            }
            for(int j = 0; j < n; j++) {
                if(board[0][j] == 'O') {
                    dfs(board, 0, j);
                }
                if(board[m - 1][j] == 'O') {
                    dfs(board, m-1, j);
                }
            }
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(board[i][j] == '.') {
                        board[i][j] = 'O';
                    } else if(board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                }
            }
        }
        void dfs(char[][] board, int i, int j) {
            board[i][j] = '.';
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    dfs(board, x, y);
                }
            }
        }
    }

    class Solution3 {
        int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
        int[] dy = {1, -1, 0, 0, 1, -1, -1, 1};
        int m, n;
        public char[][] updateBoard(char[][] board, int[] click) {
            m = board.length;
            n = board[0].length;
            int x = click[0];
            int y = click[1];
            if(board[x][y] == 'M') {
                board[x][y] = 'X';
            } else {
                dfs(board, x, y);
            }
            return board;
        }
        void dfs(char[][] board, int i, int j) {
            int count = 0;//标记此时周围的地雷数量
            for(int k = 0; k < 8; k++) {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
                    count++;
                }
            }
            if(count != 0) {
                board[i][j] = (char)('0' + count);
            } else {
                board[i][j] = 'B';
                for(int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
                        dfs(board, x, y);
                    }
                }
            }
        }
    }

}
